﻿// TopK.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<vector>
using namespace std;

//求数组内前k大的数

/// <summary>
/// 冒泡排序TopK O(NK)
/// </summary>
void TopKOnk(vector<int> &arr,int k)
{
    for (int i = 0; i < k; i++)
    {
        for (int j = arr.size() - 1; j >= i+1; j--)
        {
            if(arr[j-1]<arr[j])
                swap(arr[j], arr[j - 1]);
        }
    }
}

/// <summary>
/// 维护最小堆
/// </summary>
/// <param name="heap"></param>
/// <param name="parent"></param>
/// <param name="length"></param>
void AdjustMinHeap(vector<int>& heap, int parent, int length)
{
    int x = heap[parent];
    int child = parent * 2 + 1;
    while (child<length)
    {
        if (child+1<length && heap[child]>heap[child+1])
        {
            child++;
        }

        if (heap[child]>x)
        {
            break;
        }

        heap[parent] = heap[child];
        parent = child;
        child = parent * 2 + 1;
    }
    heap[parent] = x;
}

/// <summary>
/// 堆排序TopK O(nlogK)
/// </summary>
/// <param name="heap"></param>
/// <param name="k"></param>
void TopKOnlongK(vector<int>& heap, int k)
{
    for(int parent=k/2-1; parent >=0;parent--)
        AdjustMinHeap(heap, parent, k);
    for (int i = k; i < heap.size(); i++)
    {
        if (heap[i]>heap[0])
        {
            swap(heap[i], heap[0]);
            for (int parent = k / 2 - 1; parent >= 0; parent--)
                AdjustMinHeap(heap, parent, k);
        }
    }
}

/// <summary>
/// 左右按大小分拣（左大右小）
/// </summary>
/// <param name="arr"></param>
/// <param name="left"></param>
/// <param name="right"></param>
/// <returns></returns>
int Partition(vector<int>& arr, int left, int right)
{
    int x = arr[left];
    while (left<right)
    {
        while (left<right && x>arr[right]) right--;
        if (left<right)
        {
            arr[left] = arr[right];
            left++;
        }

        while (left < right && arr[left]>x) left++;
        if (left<right)
        {
            arr[right] = arr[left];
            right--;
        }
    }
    arr[left] = x;
    return left;
}

/// <summary>
/// 快排TopK解法 O((N/n)logk)
/// </summary>
/// <param name="arr"></param>
/// <param name="left"></param>
/// <param name="right"></param>
/// <returns></returns>
void TopKONdivNlognk(vector<int>& arr, int left, int right, int k)
{
    if (left >= right)
        return;
    int idx = 0;
    idx = Partition(arr, left, right);      //经过partition操作后可确保找到left到idx（包括idx）索引的区间数为符合要求的Topk数
    //idx==k-1便找到了前topK个数，不再进入递归(用于剪枝)
    if (idx < k-1)  //idx小于k-1时确保了left到idx（包括idx）索引的区间的数是符合要求的Topk数，左边设为idx+1向右夹边
    {
        TopKONdivNlognk(arr, idx + 1, right, k - idx);  
    }
    else if (idx > k-1)   //idx大于k-1时确保了idx到left（包括idx）索引的区间的数不是符合要求的Topk数，右边设为idx-1向左夹边
    {
        TopKONdivNlognk(arr, left, idx - 1, k);
    }
}

int main()
{
    //std::cout << "Hello World!\n";
    vector<int> arr = { 1,2,1,0,1,0,1,3,0,8 };
    //TopKOnk(arr, 3);
    //TopKOnlongK(arr, 5);
    TopKONdivNlognk(arr, 0, arr.size() - 1, 7);
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
